|
Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983. 〔N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Computing, 12:759–776, 1983.〕 The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < ''p'' < 1. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let n be the input size, ''T''(''n'') be the time complexity of the whole prune-and-search algorithm, S(n) is the time complexity of the pruning step, then ''T''(''n'') obeys the following recurrence relation: : which has the solution ''T''(''n'') = O(''S''(''n'')), since summing a geometric series only multiplies by a constant factor, namely In particular, Megiddo himself used this approach in his linear time algorithm for the linear programming problem when the dimension is fixed〔Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, 1984〕 and for the minimal enclosing sphere problem for a set of points in space.〔 ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Prune and search」の詳細全文を読む スポンサード リンク
|